package leecode

func longestSubstring(s string, k int) int {
	var chash [26]int
	for i := range s {
		chash[int(s[i]-'a')]++
	}
	var maxtypeNum int // 记录满足条件的字符种类数
	for _, v := range chash {
		if v >= k {
			maxtypeNum++
		}
	}
	var ans int
	// 通过设定窗口中不同字符的种类数来获取答案
	for typeNum := 1; typeNum <= maxtypeNum; typeNum++ {
		var hash [26]int
		var total, cnt, l int
		// 不断扩大右边界，左边界按情况收缩
		for r, ch := range s {
			idx := int(ch - 'a')
			hash[idx]++
			if hash[idx] == 1 {
				total++ //从l到，r范围的字符种类个数
			}
			// 满足种类规则只能增加一次
			if hash[idx] == k {
				cnt++ //记录当前满足条件的字符种类个数
			}
			// 缩小左边界
			for total > typeNum {
				idx = int(s[l] - 'a')
				if hash[idx] == 1 {
					total-- //种类数减1
				}
				// 对应字符的cnt只能减一次
				if hash[idx] == k {
					cnt-- //符合条件的字符种类减1
				}
				hash[idx]--
				l++
			}
			// 如果total==typeNum,且cnt==typeNum则更新答案
			if cnt == typeNum && r-l+1 > ans {
				ans = r - l + 1
			}
		}
	}
	return ans
}
